package com.dycong.common.dataStructuresAndAlgorithms.sort;


import java.util.Arrays;

/**
 * Created by dycong on 2016/12/3.
 * @see 由快速排序改变而来
 */
public class QuickSelectMin {

    public static void main(String[] args) {
        Double[] array = new java.util.Random().doubles(0, 3500000).limit(3500000).boxed().toArray(Double[]::new);
        int k = 500;
        long t = System.currentTimeMillis();
        System.out.println(quickSelectMin(array, k, true));
        System.out.println(System.currentTimeMillis() - t);


        long t1 = System.currentTimeMillis();
        System.out.println(quickSelectMin(array, k, false));
        System.out.println(System.currentTimeMillis() - t1);
    }

    /**
     * @see retain为true时花费时间相较于false时翻倍甚至更多
     * @param a
     * @param k
     * @param retain是否保留原数组结构不被破坏
     * @return
     */
    public static Comparable quickSelectMin(Comparable[] a, int k, Boolean retain) {
        if (retain) {
            Comparable[] tmp = Arrays.copyOf(a, a.length);
            quickSelect(tmp, 0, a.length - 1, k);
            return tmp[k - 1];
        } else {
            quickSelect(a, 0, a.length - 1, k);
            return a[k - 1];
        }
    }

    private static void quickSelect(Comparable[] a, int left,
                                    int right, int k) {
        if (left + 3 <= right) {
            Comparable pivot = median3(a, left, right);

            int i = left, j = right - 1;
            for (; ; ) {
                while (a[++i].compareTo(pivot) < 0) {
                }
                while (a[--j].compareTo(pivot) > 0) {
                }
                if (i < j)
                    swapReference(a, i, j);
                else
                    break;
            }

            swapReference(a, i, right - 1);   // Restore pivot
                /*todo 当k-1=i时不再进行递归调用，此时枢纽元正好在a[i]即a[i-1]!!!*/
            if (k <= i)
                quickSelect(a, left, i - 1, k);
            else if (k > i + 1)
                quickSelect(a, i + 1, right, k);
        } else  // Do an insertion sort on the subarray
            insertionSort(a, left, right);
    }

    /*todo 当swapReferences以final形式，很多编译器会以直接插入的方式编译这些代码，而不是方法调用，会提升运行速度！！*/
    public static final void swapReference(Object[] a, int index1, int index2) {
        Object tmp = a[index1];
        a[index1] = a[index2];
        a[index2] = tmp;
    }

    private static void insertionSort(Comparable[] a, int left, int right) {
        for (int p = left + 1; p <= right; p++) {
            Comparable tmp = a[p];
            int j;

            for (j = p; j > left && tmp.compareTo(a[j - 1]) < 0; j--)
                a[j] = a[j - 1];
            a[j] = tmp;
        }
    }

    /**
     * @see 取中值
     * Return median of left, center, and right.
     * Order these and hide the pivot.
     */
    private static Comparable median3(Comparable[] array, int left, int right) {
        int center = (left + right) / 2;
        if (array[center].compareTo(array[left]) < 0)
            swapReference(array, left, center);/*todo 保证C>L*/
        if (array[right].compareTo(array[left]) < 0)
            swapReference(array, left, right);/*todo 保证R>L*/
        if (array[right].compareTo(array[center]) < 0)
            swapReference(array, center, right);/*todo 保证R>C*/
            /*todo 最后R>C>P*/
        // todo Place pivot(枢轴元) at position right - 1
            /*todo 通过排序Left已经确定大于枢纽元，不再参与本次第三步(走i,j)*/
        swapReference(array, center, right - 1);
        return array[right - 1];
    }
}
